package lc;

public class Ex208 {
    class Trie {

        Node root;
        int sum;
        public Trie() {
            sum = 0;
            root = new Node();
        }
        
        public void insert(String word) {
            char[] cs = word.toCharArray();
            Node cur = root, next;
            for (char c: cs) {
                next = cur.getNext(c);
                if (next == null) {
                    cur.setNext(c);
                    next = cur.getNext(c);
                }
                next.path++;
                cur = next;
            }
            cur.setEnd();
            sum++;
        }
        
        public boolean search(String word) {
            char[] cs = word.toCharArray();
            Node cur = root, next;
            for (char c: cs) {
                next = cur.getNext(c);
                if (next == null) {
                    return false;
                }
                cur = next;
            }
            return cur.isEnd;
        }
        
        public boolean startsWith(String prefix) {
            char[] cs = prefix.toCharArray();
            Node cur = root, next;
            for (char c: cs) {
                next = cur.getNext(c);
                if (next == null || next.path != sum) {
                    return false;
                }
                cur = next;
            }
            return true;
        }
    }

    class Node {
        Node[] nexts;
        boolean isEnd;
        int path;

        public Node() {
            this.nexts = new Node[26];
            this.isEnd = false;
            this.path = 0;
        }

        public Node getNext(char c) {
            return nexts[c - 'a'];
        }

        public void setNext(char c) {
            this.nexts[c - 'a'] = new Node();
        }

        public void setEnd() {
            this.isEnd = true;
        }
    }
}
